1. Field of the Invention
The present invention relates to a method of automatically forming a combinational circuit of a large scale integration (LSI) type by use of a computer and particularly, to a method which employs a permissible function of a circuit to change an arrangement of the combinational circuit to improve operational speed of the circuit.
2. Description of the Related Art
It is presently possible to automatically form a combinational LSI circuit using a computer. Compared with a circuit designed by a skilled engineer, however, the automatically formed circuit is usually inferior in terms of the excessive number of gates, low operational speed, etc.
These matters, therefore, must be considered in designing and automatically forming the combinational circuit, or the automatically formed circuit may need to be subjected to a delay time shortening process to satisfy such design requirements.
FIG. 1 shows a standard process of combining an LSI circuit for which the present invention is applicable, and FIG. 2(A) and 2(B) explains an example of forming a combinational circuit according to a prior art. The prior art employs a computer and automatically forms the LSI combinational circuit according to the flow of FIG. 1.
In FIG. 1, a truth table 1, a two-stage product-sum logical expression 2, or a multistage network 3 of logical expressions is provided, and a technology independent combining process 4 is carried out. The term "technology independent" means that the process is done purely logically with no consideration of hardware technology such as the types of transistors and the structure of logic elements. The combining process 4 produces a multistage network of logical expressions 5, according to which a technology dependent combining process 6 is carried out to prepare a net list of gate cells indicating a connection of inputs and outputs of all cells of the circuit. According to this net list, an actual LSI is prepared.
The automatic combining process mainly comprises a multistage process of converting two-stage logical expressions into multistage logical expressions, and a technology mapping process of assigning actual circuit elements to each the multistage logical expressions, respectively. For each of the processes (assigned circuit elements), a delay time must be considered.
The multistage process sets the maximum number of stages which must not be surpassed. The maximum number of stages roughly specifies the delay time of the circuit but does not always correspond to the delay time of an actually formed circuit, so that the adjustment of the delay time cannot precisely be done based on the number of stages.
The technology mapping process uses conversion patterns or circuit equivalencies to shorten a delay time. For example, as shown in FIG. 2(A) and 2(B) a conversion pattern or equivalence circuit for the circuit of FIG 2(A) is the circuit in FIG. 2(b) whose input and output are equivalent to those of the circuit in FIG. 2(A). To shorten a delay time between a terminal A and a terminal F of the circuit of FIG. 2(A), the circuit is converted into the circuit of FIG. 2(B). This sort of conversion can precisely adjust the delay time of an actually formed circuit.
A drawback of this technique is that the conversion is always done according to predetermined conversion patterns with no exceptions. To realize a superior circuit, it is necessary to increase the kinds of conversion patterns. However, this increases the time necessary for retrieving a conversion pattern suitable for a circuit to be optimized, so that, in actual operation, the number of the conversion patterns that can be stored is time limited because of the searching process. For the same reason, the size of each conversion pattern is limited to several gates. This technique is, therefore, almost useless for a circuit whose delay time will be improved only when the entire circuit is converted into another configuration.
To solve the above problem, another prior art wholly converts the structure of a circuit according to the multistage process, and precisely adjusts the circuit according to the technology mapping process.
The efficiency of this technique is, however, is very poor because two different processes must be repeated. In addition, the two processes are not always done in harmony with each other so that they may not always effectively shorten the delay time. It is necessary, therefore, to provide a delay time shortening process that takes the delay time of an actual circuit into consideration and wholly changes the structure of the circuit.